package leetcode.dynamic;

/*

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：
    1. s[i][j] = grid[i][j] + min(grid[i][j - 1], grid[i - 1][j]);

空间压缩：
    s[i][j] 压缩为1维 ，因为可以每次从上往下或者从左往右完成遍历

 */

public class LeetCode64_MinPathSum {

    public int minPathSum(int[][] grid) {
        int[][] s = new int[grid.length + 1][grid[0].length + 1];
        for (int i = 1; i < s.length; i++){
            for (int j = 1; j < s[0].length; j++){
                s[i][j] = grid[i - 1][j - 1];
            }
        }

        for (int i = 1; i < s.length; i++){
            for (int j = 1; j < s[0].length; j++){

                if(i - 1 == 0){
                    s[i][j] += s[i][j - 1];
                    continue;
                }
                if (j - 1 == 0){
                    s[i][j] += s[i - 1][j];
                    continue;
                }

                if (s[i][j] + s[i][j - 1] > s[i][j] + s[i - 1][j]){
                    s[i][j] += s[i - 1][j];
                }else {
                    s[i][j] += s[i][j - 1];
                }
            }
        }

        return s[s.length - 1][s[0].length - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int i = new LeetCode64_MinPathSum().minPathSum(grid);
        System.out.println("i = " + i);
    }
}
